#include <unordered_map>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
        : val(0), next(nullptr) {}
    ListNode(int _val)
        : val(_val), next(nullptr) {}
    ListNode(int _val, ListNode *_next) : val(_val), next(_next) {}
};

ListNode *swapPairs(ListNode *head)
{
    if (nullptr == head || head->next == nullptr)
    {
        return head;
    }
    ListNode *newhead = new ListNode(0, head);
    ListNode *prev = newhead;

    ListNode *frontnode = prev->next, *backnode = frontnode->next,
             *nnext = backnode->next;
    while (frontnode && backnode)
    {
        prev->next = backnode;
        backnode->next = frontnode;
        frontnode->next = nnext;

        prev = frontnode;
        frontnode = nnext;

        if (frontnode)
            backnode = frontnode->next;
        if (backnode)
            nnext = backnode->next;
    }
    backnode = newhead->next; //此时backnode必为nullptr,但frontnode就不一定了
    delete newhead;
    return backnode;
}

//LRU缓存
//（哈希表+双向链表）
struct DListNode
{
    int _key;
    int _val;
    DListNode* prev;
    DListNode* next;
    DListNode(int key, int val)
        :_key(key), _val(val)
    {
        prev = next = nullptr;
    }
};
class LRUCache {
private:
    unordered_map<int, DListNode*> hashtable;
    DListNode* head;
    DListNode* tail;
    int _capacity;
    int _size;
public:
    //初始化LRUCache
    LRUCache(int capacity) {
        head = new DListNode(0,0);
        tail = new DListNode(0,0);
        head->next = tail;
        tail->prev = head;
        _capacity = capacity;
        _size = 0;
    }

    int get(int key) {
        if (hashtable.count(key))
        {
            RemoveNode(hashtable[key]);
            MoveFrontNode(hashtable[key]);
            return hashtable[key]->_val;
        }
        return -1;
    }

    void put(int key, int value) {
        //如果key,value存在
        if (hashtable.count(key))
        {
            RemoveNode(hashtable[key]);
            MoveFrontNode(hashtable[key]);
            hashtable[key]->_val = value;
        }
        else
        {
            if (_size >= _capacity)
            {
                DListNode* tmp = tail->prev;
                RemoveNode(tmp);
                hashtable.erase(tmp->_key);
                delete tmp;
                --_size;
            }
            DListNode* new_node = new DListNode(key, value);
            MoveFrontNode(new_node);
            ++_size;
            hashtable[key] = new_node;
        }
    }
    // ~LRUCache()
    // {
    //      while (head)
    //     {
    //         DListNode* tmp = head->next;
    //         delete head;
    //         head = tmp;
    //     }
    // }
public:
    void MoveFrontNode(DListNode* node)
    {
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
        node->prev = head;
    }
    void RemoveNode(DListNode* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};
